The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.
Network devices, such as network switches, bridges, routers, etc., typically perform longest prefix match lookups for routing packets that traverse a network device. Generally speaking, a routing table associates network addresses with next hops to which packets associated the network addresses should be transmitted from a network device. A longest prefix match lookup involves searching a routing table based on a network address associated with a packet to find a routing entry that matches the largest number of leading bits of the address. Some network devices use Ternary Content Addressable Memory (TCAM) technology-based routing tables. In a TCAM-based routing table, all entries of the routing table can be searched in parallel based on an address to find an entry having a longest prefix match for the address. Therefore, TCAM devices allow longest prefix match searches to be performed relatively quickly. However, TCAM devices are generally expensive in terms of size, cost and power consumption.
As an alternative to TCAM implementations, some network devices use random access memory devices, such as static random access memory (SRAM) devices or dynamic random access memory (DRAM) devices, for storing routing tables, and employ searching algorithms, such as trie-based algorithms to perform longest prefix match searches in the routing table. However, a RAM-based routing table typically requires more memory space and a higher memory bandwidth compared to a TCAM-based routing table of comparable size. Also, the searching algorithms typically employed to search such RAM-based routing tables are relatively slow and do not necessarily operate at high line rates supported by many network devices. Moreover, such RAM-based routing tables and searching algorithms do not scale well to readily handle the increasing length network addresses.